// 字符串
// 常见题型 - 找最长公共前缀 - 统一对比
// 常见题型 - 找回文串 - 用中心扩展算法
// 常见题型 - 高精度模拟加减乘除法，需要按照题意进行模拟
// 常见题型 - 首先将字符串逆序，模拟两数相乘，可以先模拟 无进位相乘，再模拟 两数相加，处理进位

// 例题 4：
// 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
//        注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
//
//        示例 1:
//
//        输入: num1 = "2", num2 = "3"
//        输出: "6"
//        示例 2:
//
//        输入: num1 = "123", num2 = "456"
//        输出: "56088"
//
//        提示：
//
//        1 <= num1.length, num2.length <= 200
//        num1 和 num2 只能由数字组成。
//        num1 和 num2 都不包含任何前导零，除了数字0本身。

// 解题思路：
// 注意将字符转化为数字
// 将字符串逆序，可以使用接口，也可以使用双指针进行逆序
// 模拟两数相乘
// 模拟两数无进位相乘，再模拟两数相加，处理进位

public class Multiply {
    // 解法 1：按照列竖式运算模拟两数相乘
    public String multiply1(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        StringBuilder n1 = new StringBuilder(num1);
        StringBuilder n2 = new StringBuilder(num2);
        n1.reverse();
        n2.reverse();
        char[] arr1 = n1.toString().toCharArray();
        char[] arr2 = n2.toString().toCharArray();
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < len1; i++){
            int t = 0;
            int pos = 0;
            StringBuilder tmp = new StringBuilder();
            for(int j = 0; j < i; j++) tmp.append(0);
            while(pos < len2 || t > 0){
                if(pos < len2) t += (arr1[i] - '0') * (arr2[pos] - '0');
                tmp.append(t % 10);
                t /= 10;
                pos++;
            }
            StringBuilder res = new StringBuilder();
            int lenRet = ret.length();
            int lenTmp = tmp.length();
            char[] retArr = ret.toString().toCharArray();
            char[] tmpArr = tmp.toString().toCharArray();
            pos = 0;
            t = 0;
            while(pos < lenRet || pos < lenTmp || t > 0){
                if(pos < lenRet) t += retArr[pos] - '0';
                if(pos < lenTmp) t += tmpArr[pos] - '0';
                res.append(t % 10);
                t /= 10;
                pos++;
            }
            ret = res;
        }
        return ret.reverse().toString();
    }
    // 解法 2：先模拟无进位相乘，再模拟两数相加
    public String multiply2(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        StringBuilder n1 = new StringBuilder(num1);
        StringBuilder n2 = new StringBuilder(num2);
        n1.reverse();
        n2.reverse();
        char[] arr1 = n1.toString().toCharArray();
        char[] arr2 = n2.toString().toCharArray();
        int[] res = new int[len1 + len2 - 1];
        for(int i = 0; i < len1; i++){
            for(int j = 0; j < len2; j++){
                res[i + j] += (arr1[i] - '0') * (arr2[j] - '0');
            }
        }
        StringBuilder ret = new StringBuilder();
        int t = 0;
        int pos = 0;
        while(pos < len1 + len2 - 1 || t > 0){
            if(pos < len1 + len2 - 1) t += res[pos];
            ret.append(t % 10);
            t /= 10;
            pos++;
        }
        return ret.reverse().toString();
    }
}
